package com.fanshuai.algorithms.branch;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 单源最短路径  分支限界法实现
 * 给定带权有向图G＝(V，E)，其中每条边的权是非负实数。给定V中的一个顶点，称为源。
 * 要计算从源到所有其它各顶点的最短路长度，这里路的长度是指路上各边权之和。
 *
 * 分支限界法通过BFS实现，实现方式为：
 * 定义遍历节点，节点绑定当前节点索引值，及最优解信息等；
 * 定义分支限界函数，达到剪枝目的
 * 通过BFS不断遍历子节点，更新最优解
 *
 * 获得最优解的路径为解向量，解向量求解方式为：
 * （1）每个节点绑定当前解向量，在BFS遍历过程中，不断更新解向量，最终得到最优解向量，此方法比较耗费空间
 * （2）每个节点绑定指向父节点指针，最终形成一个指向父节点的树；从当前节点回溯到根节点，得到最优解向量
 */
public class MinPath {
    /**
     * 单源最短路径
     * @param matrix  邻接矩阵
     */
    public static int minPath(int[][] matrix, int src, int desc, List<Integer> path) throws Exception {
        int n = matrix.length;
        int[] dist = new int[n];  //各节点到src节点最短路径, 节点编号为[1..n]
        int[] parent = new int[n]; //各节点的父节点, 节点编号为[1..n]
        dist[src] = 0; //最优解数组
        parent[src] = src; //指向父节点的树
        for (int i = 0; i < n && i != src; i++) {
            dist[i] = Integer.MAX_VALUE; //其他节点最短路径初始化为inf
            parent[i] = -1; //父节点初始化为-1
        }

        //广度优先遍历
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(src);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int j = 0; j < n && j != cur; j++) { //节点编号为[0..n-1]
                if (matrix[cur][j] < Integer.MAX_VALUE && dist[cur] + matrix[cur][j] < dist[j]) {
                    dist[j] = dist[cur] + matrix[cur][j];
                    parent[j] = cur;

                    queue.add(j);
                }
            }
        }

        int i = desc;
        while (parent[i] != i && parent[i] != -1) { //通过指向父节点的树，计算最短路径
            path.add(i);
            i = parent[i];
        }
        if (parent[i] != -1) {
            path.add(i);
        }
        reverse(path);

        return dist[desc];
    }

    private static void reverse(List<Integer> list) {
        if (null == list || list.size() == 0) {
            return;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            int temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);

            i++;
            j--;
        }
    }

    public static void main(String[] args) throws Exception {
        String path = System.getProperty("user.dir") + "/src/main/java/com/fanshuai/algorithms/branch/";
        List<String> lines = Files.readAllLines(Paths.get(path + "graph1"));

        int n = Integer.valueOf(lines.get(0));
        int[][] matrix = new int[n + 1][n + 1]; //有向图
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                matrix[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 2; i < lines.size(); i++) {
            String line = lines.get(i);
            String[] arr = line.split(" ");

            int x = Integer.valueOf(arr[0]);
            int y = Integer.valueOf(arr[1]);
            int weight = Integer.valueOf(arr[2]);

            matrix[x][y] = weight;
        }
        int[][] pairs = new int[][] {{1, 2}, {1, 3}, {1, 4}, {1, 5},
                {1, 6}, {3, 4}, {3, 6}, {4, 6}};

        for (int[] pair: pairs) {
            List<Integer> list = new ArrayList<>();
            int min = minPath(matrix, pair[0], pair[1], list);

            System.out.println(String.format("min path=%d, path=%s", min, list));
        }
    }
}
